ATM network communications are connection type communications in which connections are preset. Such connection information as destination information, transfer priority information, bandwidth monitoring information, etc. corresponding to each connection is registered in each ATM of an ATM network. An ATM performs such processings as cell transferring, priority-based transferring, and bandwidth monitoring according to the connection information corresponding to the connection identifier written in each cell header.
On the other hand, IP network communications are connectionless type communications in which no connection is preset. Consequently, when enabling a router in an IP network to perform priority-based transferring and bandwidth monitoring, the router is required to have flow detecting means. A flow or a packet flow means a flow of a series of packets decided by a combination of header information in the header fields. A condition generated by a combination of header information in the header fields is referred to as a flow condition. The detecting of a packet flow as matching/unmatching with the above flow condition is referred to as flow detection. And, such packet processings as priority-based transferring, bandwidth monitoring, filtering, statistical information collecting, etc. performed with respect to each packet flow are referred to as flow processings. The flow detecting means detects a packet flow from the header information of a packet. The header information includes an IP address, etc. A router performs such flow processings as priority-based transferring and bandwidth monitoring according to the priority-based transferring information and the bandwidth monitoring information corresponding to each flow.
A router is also required to detect packet flows so as to filter the packets. In the case of the connection type communication, a connection is preset only for each permitted opposite party and the registration of connection is disabled for non-permitted opposite parties to prevent receiving cells from unexpected opposite parties. This is why the communication security is easily assured in the connection type communications. In the case of the connectionless type communication, however, packets are possibly received from all the terminals connected to the subject network. This is why packets are required to be filtered to discard those received from unexpected opposite parties via connectionless type communications.
A router is also required to have flow detecting means to collect statistic information of each flow. The statistical information items to be collected are, for example, the number of packets and the number of bytes inputted to each router, as well as those output from the router or those discarded by the router.
To keep the communication quality in an IP network, each router in this network is required to have the above described flow detecting means to be used for priority-based transferring of packets. When some of the routers in an IP network do not perform such priority-based transferring of packets, the communication quality is degraded by those routers thereby degrading the communication quality of the whole network. The flow detecting means, when it is provided for the backbone router located in the backbone of an IP network, becomes a bottleneck for fast transferring of packets, since the backbone router uses fast lines to handle many more packet flows than edge routers.
The Differentiated Service (Diffserv) technique disclosed in RFC2475 (hereinafter “Document 1”) is used to solve this problem. Hereunder, the Diffserv is described with reference to FIG. 3. An edge router A326/B327 (referred to as a boundary node in the Document 1) located at the inlet of the internet 325, when receiving a packet from a site A321, B322, C323, D324, detects the flow based on such information items as the source/destination IP address, the source/destination port number, a protocol, etc. written in the TCP/IP header of the packet. The edge router A326/B327 then monitors the bandwidth used by the detected flow of packets to decide the transfer priority of the flow in the Internet 325. In the case of the IPv6 protocol, this information is written in the Traffic Class (TC) field of each packet. In the case of the IPv4 protocol, the information is written in the Differentiated Service Code Point (DSCP) field. The backbone router 328 (referred as the interior node in the Document 1) located at the backbone of the Internet 325 performs priority-based transferring of the flow referred as the Per Hop Behavior (PHB) according to the TC thereby keeping the communication quality in the Internet 325. When a network employs the Diffserv, only the edge routers A326 and B327 located at the inlet of the Internet 325 are required to have the flow detecting means respectively, while the backbone router 328 is not.
The flow detecting means that realizes this boundary node is described in, for example, “a flow identification method with the use of an contents addressable memory”, shown in FIG. 15, written by Uga and others in a collection of lectures/papers at the 2000 comprehensive meeting of Denshi Jouhou Tsuushin Gakkai SB-4-2 (hereinafter “Document 2”). The flow detecting means that employs the technique described in the Document 2 includes a CAM (Contents Addressable Memory) 1501 for storing flow entries 1510-j (j=1 to M) (each describing a flow condition generated by a combination of the header information, etc.) as well as a retrieval result retaining table 1502 for storing retrieval result entries 1520-j (each describing an operation corresponding to a flow entry 1510-j). The flow detecting means, when detecting a packet flow, makes a comparison of matching/unmatching between the contents of the packet header information and of the flow entry 1510-j. Then, the flow detecting means writes TOS (=DSCP) in each packet. The TOS is described in the retrieval result entry 1520-j corresponding to a matching flow entry 1510-j. 
The backbone router of a network that employs the Diffserv is not required to have such flow detecting means to maintain the communication quality. However, the backbone router is required to have the flow detecting means to perform other flow processings (ex., collecting of statistical information).
Hereunder, why the backbone router is required to have such the flow detecting means is described in detail with reference to FIG. 3. Sites A321 and C323 shown in FIG. 3 both belong to a corporation A. This corporation A uses the Internet 325 to transfer data from the site A 321 to the site C323 at a transfer rate of 10 Mbits/sec. Similarly, sites B322 and D324 both belong to a corporation B and this corporation B uses the Internet 325 to transfer data from the site B322 to the site D324 at a transfer rate of 10 Mbits/sec. On the other hand, the Internet 325 guarantee transferring of packets at a rate of 10 Mbits/sec and confirms with the managers of the corporations A and B that the internet service contracts with them fulfill their transfer rate requirements.
When the Internet 325 employs the technique disclosed in the Document 1, each router acts as follows. When the edge router A326 receives a packet from the site A321/B322, the flow detecting means of the edge router A326 identifies the source site from the source IP address written in the packet and monitors the bandwidth used by the site. When the packet uses a bandwidth whose transfer rate is below the internet service contracted one (10 Mbits/sec), the flow detecting means writes the value of “priority” in the TC of the packet. When the packet flow uses a bandwidth whose transfer rate is over the internet service contracted one, the flow detecting means writes the value of “non-priority” in the TC. Respective packets having “priority” written in TC are referred to as priority packets and respective packets having “non-priority” written in TC are referred to as non-priority packets. The edge routers A326 and B327 as well as the backbone router 328 in the Internet 325 perform priority-based transferring according to the TC value respectively to assure the transferring of priority packets as desired. In addition, each of those routers distinguishes among TCs (i.e., transfer priority levels) to count such statistical information items as the number of packets/bytes discarded for each of the source sites. The internet service provider (“ISP”), since no priority packet is discarded during transferring, can assure the managers of the corporations A and B of the fulfillment of their internet service contracts.
The backbone router 328 and the edge router B327 are not required to have any flow detecting means to conduct priority-based transferring of packet flows (i.e., to maintain the communication quality). To collect statistical information, however, those routers are required to have such means to detect each packet flow from the source IP address repetitively so as to identify each source site. At this time, the flow detecting means of the backbone router that uses fast lines often becomes a bottleneck that degrades the transfer performance of the network. The Document 2 does not describe any method to omit the flow detecting means from the backbone router 328.
Routers that employ the above conventional technique have a problem that the number of flow detecting means increases with the increase of the number of flow processings. Generally, the cost of a router increases as the number of flow detecting means increases. The edge router A326 is required to identify each site and monitor the bandwidth used by the site, as well as to collect the number of packets/bytes discarded for each TC. And, even when the edge router A326 detects a flow and identifies the source site through bandwidth monitoring, the edge router 326 is still required to detect each flow from the source IP address repetitively so as to identify the source site and collect statistical information. This is why the number of flow detecting means increases when the number of flow processings increases in each router according to the conventional technique.
In addition to the above problem, the conventional technique has another problem that it is impossible to perform bandwidth monitoring and statistical information collecting with respect to each flow bundle consisting of a plurality of flows if the flows in each bundle can not be distinguished from each other. On the other hand, each router is required to perform such bandwidth monitoring for each flow bundle consisting of a plurality of flows as described above. In the case of statistical information collecting, each router is also required to count the sum of byte lengths of input/output packets and the number of input/output packets, as well as those discarded therefrom with respect to each flow bundle.
Next, a problem of each router employing the technique described in the Document 2 is described in detail with reference to FIG. 2. Via the IP network shown in FIG. 2, sites A210 and B220 of a corporation are connected to a site C230 of the same corporation. An internet service contract is made between the internet service provider and the manager of the corporation network so as to transfer packet flows from the site A210 or B220 to the site C230 at a rate of 10 Mbits/sec. The packet flow output from the site A210 is designated as the flow 1 and the packet flow output from the site B220 is designated as the flow 2. The terminals A212 and B213 of the site A210 as well as the terminals C222 and D223 of the site B220 send packets to the terminal E232 of the site C230 via the Internet 200. The edge router A202 located at an edge of the Internet 200 monitors the bandwidths of the packets sent from both of the sites A210 and B220 at a rate of 10 Mbits/sec.
Assuming that the edge router A202 employing the technique described in the Document 2 monitors the bandwidth of the packets in the flow 1 at a rate of 10 Mbits/sec, the edge router A202 sets the identifier of the line 206 connected to a gateway router A211 in the flow entry 1510-1. The edge router A202 then initializes such packet arrival history information as the arrival time, etc. of the previous packet in the retrieval result entry 1520-1 and updates the bandwidth monitoring information as a value corresponding to 10M bits/sec. When a packet of the flow 1 is inputted, the edge router A202 refers back to the packet arrival history information and the monitoring bandwidth information in the retrieval result entry 1520-1 (corresponding to the flow entry 1510-1 to monitor the bandwidth and update the packet arrival history information).
Next, the monitoring of the bandwidths of the flows 1 and 2 of packets is described below. An OR operation of flow conditions cannot be set in the flow entry 1510 such that it is impossible to describe a flow of packets inputted via the line 206 and a flow of packets inputted via the line 207 in one flow entry 1510-j. However, if the line 206 and the line 207 are described as flow conditions in two flow entries 1510-1 and 1510-2, the packet arrival history information to be updated in will differ between flow entries 1510-1 and 1510-2, depending on the input site. To monitor the bandwidths of both flows 1 and 2 simultaneously, it is required to refer back to the same packet arrival history information and update the information regardless of the input site. Nevertheless, routers that employ the conventional technique 1 cannot monitor the bandwidth of each flow bundle consisting of a plurality of flows as described above.
Next, how an edge router collects statistical information is described with reference to FIG. 2. The edge router A202 shown in FIG. 2 counts the sum of bytes in each packet and/or the number of packets output from the sites A210 and B220 collectively. The internet service provider reads those statistical information items periodically from the edge router A202 at the management terminal 205 to use those information items, for example, for accounting.
First, how the edge router A202 employing the technique described in the Document 2 counts a sum of bytes in each packet and/or the number of packets in the flow 1 is described. At this time, the edge router A202 sets an identifier for the line 206 connected to the gateway router A211 in the flow entry 1510-1 so as to identify the flow 1. In addition, the edge router A202 initializes the retrieval result entry 1520-1 to “0”. The entry 1520-1 is composed of a byte counter that counts a sum of bytes in each packet and a packet counter that counts the number of packets. Receiving a packet of the flow 1, the edge router A202 reads the values of the byte counter and of the packet counter (corresponding to the flow entry 1510-1) and adds “1” and the number of bytes in the received packet to the values of the counters respectively. The edge router A202 then writes the updated values of the counters in the same retrieval result entry 1520-1.
Next, the counting of the sum of bytes in each packet and/or of the number of packets in each of the flows 1 and 2 collectively is described. Because the flow entry 1510-j cannot describe the logical sum (OR) of flow conditions, it is impossible to describe a packet flow inputted via the line 206 and a packet flow inputted via the line 207 in one flow entry 1510 as discussed above. In addition, if two flow entries 1510-1 and 1510-2 in which lines 206 and 207 are described as flow conditions are set for describing those packet flows, the edge router A202 refers back to wrong byte and packet counters thereby updating the counters with wrong values. This is why each router employing the conventional technique 1 cannot count a sum of bytes in each input/output packet and/or the number of input/output packets in each flow with respect to each flow bundle as discussed above. As an example, there are only two sites sending out packet flows in FIG. 2. There might be more sites in actual operation. When the number of sites increases, the management terminal 205 is required to read more statistical information from the edge router A202 such that the capacity of the transmission bandwidth between the management terminal 205 and the edge router A202 and/or the capacity of the memory of the management terminal 205 for storing the statistical information becomes insufficient. Consequently, the edge router A202 is also required to collect summarized statistical information.
While the technique described in the Document 2 fails to solve all the mentioned problems, the technique described in the Document 1 also fails to solve a problem that bandwidth monitoring and statistical information collecting with respect to each flow bundle can not be described in the flow entry.